|
In graph theory, the Poussin graph is a particular graph with 15 vertices and 39 edges. == History == In 1879, Alfred Kempe published a proof of the four color theorem, one of the big conjectures in graph theory .〔Kempe, A. B. "On the Geographical Problem of Four-Colors." Amer. J. Math. 2, 193–200, 1879.〕 While the theorem is true, Kempe's proof is incorrect.. Heawood illustrates it in 1890 〔P. J. Heawood, "Map colour theorem", Quart. J. Pure Appl. Math. 24 (1890), 332–338.〕 with a counter-example, and Vallée Poussin reaches the same conclusion in 1896 with the Poussin graph .〔R. A. Wilson, Graphs, colourings and the four-colour theorem, Oxford University Press, Oxford, 2002. MR 2003c:05095 Zbl 1007.05002.〕 Kempe's (inorrect) proof is based on alternating chains, and as those chains prove useful in graph theory mathematicians remain interested in such counter-examples. More were found later: first, the Errera graph in 1921 〔Errera, A. "Du coloriage des cartes et de quelques questions d'analysis situs." Ph.D. thesis. 1921.〕 ,〔Peter Heinig. (Proof that the Errera Graph is a narrow Kempe-Impasse ). 2007.〕 then the Kittell graph in 1935, with 23 vertices ,〔Kittell, I. "A Group of Operations on a Partially Colored Map." Bull. Amer. Math. Soc. 41, 407–413, 1935.〕 and finally two minimal counter-examples (the Soifer graph in 1997 and the Fritsch graph in 1998, both of order 9) 〔A. Soifer, “Map coloring in the victorian age: problems and history”, Mathematics Competitions 10 (1997), 20–31.〕 〔R. Fritsch and G. Fritsch, The Four-Color Theorem, Springer, New York, 1998. MR 99i:05079.〕 .〔Gethner, E. and Springer, W. M. II. « How False Is Kempe's Proof of the Four-Color Theorem? » Congr. Numer. 164, 159–175, 2003.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Poussin graph」の詳細全文を読む スポンサード リンク
|